package cg.studio.practise;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class WordSequence
{
  private static void log( String message )
  {
    System.out.println( message );
  }
  
  public static void main( String[] argv )
  {
    while( true )
    {
      try
      {
        System.out.println( "please input a word: " );
        BufferedReader reader = new BufferedReader( new InputStreamReader( System.in ) );
        String word = reader.readLine();
        if( word.length() < 2 )
        {
          System.out.println( "We expecting more than 2 chars." );
          continue;
        }
        
        System.out.println( "the sequence number of '" + word + "' is: " + ( getWordSequence(word)+1 ) );
      }
      catch( IOException e )
      {
        e.printStackTrace();
      }
    }
  }
  
  private static int getWordSequence( String word )
  {
    if( word.isEmpty() )
      throw new IllegalArgumentException( "we are not expecting this. must be something wrong." );
    
    if( word.length() == 1 )
      return 0;
    
    word = word.toUpperCase();
    char[] chars = word.toCharArray();
    int[] charCount = new int[ 'Z'-'A' + 1 ]; 
    for( char c : chars )
    {
      charCount[c-'A'] += 1;
    }
    
    return getWordSequence( word, charCount );
  }
  
  private static int getWordSequence( String word, int[] charCount )
  {
    char[] chars = word.toCharArray();
    int index = 0;
    int numberOfAllDistinctChar = getNumberOfDistinctChar( charCount );

    // count the number of words which start with chars less than the begin of word;
    char c = chars[0];
//    int numberOfDistinctChar = getNumberOfDistinctCharLessThan( c, charCount);
    
    for( char startChar = 'A'; startChar < c; ++startChar )
    {
      int startCharIndex = startChar-'A'; 
      if( charCount[startCharIndex] == 0 )
        continue;
      // all words start with <startChar> is less than input word
      charCount[ startCharIndex ] -= 1;
      index += getAllWordNumber( charCount );
      charCount[ startCharIndex ] += 1;  //recover;
    }
    
    // count the number of words which start with same beginning char
    index += getWordSequence( word.substring( 1 ) );
    
    log( "\tword sequence for " + word + " is: " + index );
    return index;
  }

  // let's say AAABBC, when insert second A, divide two; insert 3rd A, divide three; etc
  private static int getAllWordNumber( final int[] charCount )
  {
    int number = 1;
    int totalSeq = 0;
    for( int index = 0; index < 'Z'-'A'; ++index )
    {
      int count = charCount[ index ];
      if( count == 0 )
        continue;
      for( int i=1; i<=count; ++i )
      {
        number *= ++totalSeq;
        number /= i;
      }
    }
    return number;
  }

//  private static int getNumberOfDistinctCharLessThan( char c, int[] charCount )
//  {
//    int numberOfChar = 0;
//    for( int index = c-'A'-1; index >= 0; --index )
//    {
//      numberOfChar += ( charCount[ index ] > 0 ? 1 : 0 );
//    }
//    return numberOfChar;
//  }
  
  private static int getNumberOfDistinctChar( int[] charCount )
  {
    int numberOfChar = 0;
    for( int index = 0; index <= 'Z'-'A'; ++index )
    {
      numberOfChar += ( charCount[ index ] > 0 ? 1 : 0 );
    }
    return numberOfChar;
  }
}
